package shuati.od24D;

import java.util.ArrayList;

/**
 * @author : LdLtd
 * @Date : 2024/7/10
 * @Description:
 * 小扇和小船今天又玩起来了数字游戏，
 *
 * 小船给小扇一个正整数 n（1 ≤ n ≤ 1e9），小扇需要找到一个比 n 大的数字 m，使得 m 和 n 对应的二进制中 1 的个数要相同，如：
 *
 * 4对应二进制100
 *
 * 8对应二进制1000
 *
 * 其中1的个数都为1个
 * 现在求 m 的最小值。
 *
 * 输入描述
 * 输入一个正整数 n（1 ≤ n ≤ 1e9）
 *
 * 输出描述
 * 输出一个正整数 m
 *
 * 示例1
 * 输入：
 * 2
 *
 * 输出：
 * 4
 *
 * 说明：
 * 2的二进制10，
 * 4的二进制位100，
 * 1的个数相同，且4是满足条件的最小数
 * 示例2
 * 输入：
 * 7
 *
 * 输出：
 * 11
 *
 * 说明：
 * 7的二进制111，
 * 11的二进制位1011，
 * 1的个数相同，且11是满足条件的最小数
 * 题解
 * 题解分析
 * 这道题目要求找到一个比给定的正整数 n 大的数字 m，使得它们的二进制表示中 1 的个数相同。本质上，题目要求在二进制表示中，找到一个比 n 大的具有相同数量的 1 的数。
 *
 * 给出的解法是使用贪心算法。首先，将 n 转换为二进制表示，然后通过贪心地找到可以将某个 0 变成 1 的位置，使得数字变大，同时保持 1 的个数不变。最后输出这个结果。
 *
 * 解题思路
 * 将给定的十进制数 n 转换为二进制表示，并在末尾添加一个 0。
 * 使用贪心算法找到可以将某个 0 变成 1 的位置的索引 idx。
 * 调整 idx 位 0 变成 1，同时调整 idx 前的位，使得低位为 1，高位为 0，且二进制中 1 的个数不变。
 * 输出调整后的结果。
 *
 * 作者：code5bug
 * 链接：https://www.nowcoder.com/discuss/594935481876361216
 * 来源：牛客网
 */
public class NextNumberWithSameOnes {
    public static void main(String[] args) {
        int n = 19; // 示例输入
        System.out.println(getNextNumberWithSameOnes(n));
    }

    public static int getNextNumberWithSameOnes(int n) {
        ArrayList<Integer> ar = new ArrayList<>();
        while (n > 0) {
            ar.add(n % 2);
            n /= 2;
        }
        ar.add(0);
        int idx = 0, ne = 0;
        for (; idx < ar.size(); idx++) {
            if (ne > 0 && ar.get(idx) == 0) {
                break;
            }
            ne += ar.get(idx);
        }
        // 将 idx 之前的 1 都变成 0
        for (int i = 0; i < idx; i++) {
            ar.set(i, 0);
        }
        // 将 idx 位置的 0 变成 1
        ar.set(idx, 1);
        // 将 idx 之前的 1 都放到最低位
        for (int i = 0; i < ne - 1; i++) {
            ar.set(i, 1);
        }
        // 计算结果
        int res = 0;
        for (int i = ar.size() - 1; i >= 0; i--) {
            res = res * 2 + ar.get(i);
        }
        return res;
    }
}